剑指Offer 13. 机器人的运动范围。
解答1[Java]:递归算法
核心思想
回溯的思想。
使用一个布尔类型的数组标记所有格子是都已经被访问过了。
代码
public class Solution {
public int movingCount(int threshold, int rows, int columns) {
if (threshold < 0 || rows <= 0 || columns <= 0) {
return 0;
}
boolean[] visited = new boolean[rows * columns];
int count = 0;
count = movingCountCore(threshold, rows, columns, 0, 0, visited);
return count;
}
private int movingCountCore(int threshold, int rows, int columns, int row, int column, boolean[] visited) {
int count = 0;
if (check(threshold, rows, columns, row, column, visited)) {
visited[row * columns + column] = true;
count = 1 + movingCountCore(threshold, rows, columns, row - 1, column, visited)
+ movingCountCore(threshold, rows, columns, row + 1, column, visited)
+ movingCountCore(threshold, rows, columns, row, column - 1, visited)
+ movingCountCore(threshold, rows, columns, row, column + 1, visited);
}
return count;
}
private boolean check(int threshold, int rows, int columns, int row, int column, boolean[] visited) {
return row >= 0 && row < rows && column >= 0 && column < columns
&& getDigitSum(row) + getDigitSum(column) <= threshold
&& !visited[row * columns + column];
}
private int getDigitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}
解答2[Java]:非递归算法
核心思想
代码
import java.util.Stack;
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
if (rows <= 0 || cols <= 0 || threshold < 0) {
return 0;
}
Stack<Integer> s = new Stack<>();
boolean[] visited = new boolean[rows * cols];
int[][] xoy = {{0, 1, 0, -1}, {1, 0, -1, 0}};
int count = 0;
s.add(0);
visited[0] = true;
while (!s.empty()) {
int cur = s.pop();
count++;
// 一个格子的坐标可以根据线性顺序和列数算出
for (int i = 0; i < 4; i++) {
int x = cur % cols + xoy[0][i];
int y = cur / cols + xoy[1][i];
int sum = getDigitSum(x) + getDigitSum(y);
if (x >= 0 && x < cols && y >= 0 && y < rows
&& sum <= threshold && !visited[x + y * cols]) {
s.add(x + y * cols);
visited[x + y * cols] = true;
}
}
}
return count;
}
private int getDigitSum(int i) {
int sum = 0;
while (i > 0) {
sum += i % 10;
i /= 10;
}
return sum;
}
}